#include <iostream>

void QuickSort(int* arr, int left, int right)
{
    if(left >= right)
    {
        return;
    }
    int key = left;
    int begin = left, end = right;
    while(left < right)
    {
        while(left < right && arr[right] >= arr[key])
        {
            right--;
        }
        while(left < right && arr[left] <= arr[key])
        {
            left++;
        }
        std::swap(arr[left], arr[right]);
    }
    std::swap(arr[left], arr[key]);
    key = left;
    QuickSort(arr, begin, key - 1);
    QuickSort(arr, key + 1, end);
}

int main()
{
    int arr[10] = {2, 5, 1, 8, 6, 3, 7, 0, 9, 4};
    int sz = sizeof(arr)/sizeof(int);
    QuickSort(arr, 0, sz - 1);
    for(int i = 0; i < sz; i++)
    {
        std::cout << arr[i] << std::endl;
    }

    return 0;
}
